Ćwiczenia/3. Ćwiczenia/Zadanie 2. (Wstawianie elementu do kopca binarnego).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaimplementować funkcję wstawiającą dowolny element do kopca binarnego."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ nie jest powiedziane, o jaki kopiec chodzi (Min Heap, czy Max Heap), poniżej prezentuję rozwiązanie dla obu kopców. W rozwiązaniach znajduje się zarówno wersja obiektowa oraz funkcyjna. W poniższych implementacjach ograniczam się do koniecznych metod do utworzenia kopca oraz dodania wartości (nie załączam metod, które usuwają odpowiednio największą/najmniejszą wartość lub ją odczytują). Pełna implementacja kopców znajduje się w <a href=\"../../../%23Kolokwium/Jupyter-notebooks/Drzewiaste struktury danych.ipynb\">TYM</a> pliku."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja wypisująca kopiec binarny (nie jest częścią algorytmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def complete_tree_string(values):\n",
    "    if values:\n",
    "        just = 0\n",
    "        data = []\n",
    "\n",
    "        limit = 1\n",
    "        values_row = []\n",
    "        branches_row = []\n",
    "        prev_nodes = 0\n",
    "\n",
    "        for i in range(1, len(values) + 1):\n",
    "            curr_nodes = i - prev_nodes\n",
    "            val_str = str(values[i-1])\n",
    "            just = max(just, len(val_str))\n",
    "            values_row.append(val_str)\n",
    "            right_child_idx = 2 * i\n",
    "            left_child_idx = right_child_idx - 1\n",
    "            if left_child_idx < len(values):\n",
    "                branches_row.append('/')\n",
    "            if right_child_idx < len(values):\n",
    "                branches_row.append('\\\\')\n",
    "\n",
    "            if curr_nodes == limit: \n",
    "                prev_nodes = i\n",
    "                limit *= 2\n",
    "                data.append([values_row, branches_row])\n",
    "                values_row = []\n",
    "                branches_row = []\n",
    "\n",
    "        if values_row:\n",
    "            data.append([values_row, branches_row])\n",
    "\n",
    "        begin_sep = sep = 3 if just % 2 else 2\n",
    "        data_iter = iter(data[::-1])\n",
    "        result = [''] * (len(data) * 2 - 1)\n",
    "        result[-1] = (' ' * sep).join(val.center(just) for val in next(data_iter)[0])\n",
    "\n",
    "        # Format the tree string\n",
    "        for i, (values, branches) in enumerate(data_iter):\n",
    "            mul = 2 * i + 1\n",
    "            # Values\n",
    "            indent = (2 ** (i + 1) - 1) * (just + begin_sep) // 2\n",
    "            sep = 2 * sep + just\n",
    "            result[-(mul + 2)] = f\"{' ' * indent}{(' ' * sep).join(val.center(just) for val in values)}\"\n",
    "            # Branches\n",
    "            branch_indent = (3 * indent + just) // 4\n",
    "            branches_row = []\n",
    "            d_indent = indent - branch_indent\n",
    "            branches_sep = ' ' * (2 * (d_indent - 1) + just)\n",
    "            for i in range(0, len(branches), 2):\n",
    "                branches_row.append(f\"{branches[i]}{branches_sep}{branches[i + 1] if i + 1 < len(branches) else ''}\")\n",
    "            result[-(mul + 1)] = f\"{' ' * branch_indent}{(' ' * (sep - 2 * d_indent)).join(branches_row)}\"\n",
    "\n",
    "        return '\\n'.join(result)\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Max Heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu #1 (obiektowy kopiec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxHeap:\n",
    "    def __init__(self, values=None):\n",
    "        if values:\n",
    "            self.heap = list(values) # We make a copy of values in order not to modify them\n",
    "            self.build_heap()\n",
    "        else:\n",
    "            self.heap = []\n",
    "        \n",
    "    def __str__(self):  # A 'complete_tree_string' function is required in order to ensure that printing works\n",
    "        return complete_tree_string(self.heap)\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return bool(self.heap)\n",
    "    \n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def insert(self, val: object):\n",
    "        # Add a value as the last node of out Complete Binary Tree\n",
    "        self.heap.append(val)\n",
    "        # Fix heap in order to satisfy a max-heap property\n",
    "        self._heapify_up(self.heap_size - 1)\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "        \n",
    "    def _heapify_up(self, curr_idx, end_idx=0):\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self.parent_idx(curr_idx)\n",
    "            if self.heap[curr_idx] > self.heap[parent_idx]:\n",
    "                self.swap(curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):\n",
    "        # Loop till the current node has a child larger than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # smaller than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a max-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            largest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.heap[l] > self.heap[curr_idx]: \n",
    "                    largest_idx = l\n",
    "                if r < end_idx and self.heap[r] > self.heap[largest_idx]:\n",
    "                    largest_idx = r\n",
    "\n",
    "            if largest_idx != curr_idx:\n",
    "                self.swap(curr_idx, largest_idx)\n",
    "                curr_idx = largest_idx\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "    def build_heap(self):\n",
    "        for i in range(self.heap_size // 2 - 1, -1, -1):\n",
    "            self._heapify_down(i, self.heap_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  2\n",
      " / \\\n",
      "1   0\n",
      "\n",
      "      2\n",
      "    /   \\\n",
      "  2       0\n",
      " / \n",
      "1\n",
      "\n",
      "      2\n",
      "    /   \\\n",
      "  2       0\n",
      " / \\\n",
      "1   0\n",
      "\n",
      "      6\n",
      "    /   \\\n",
      "  2       2\n",
      " / \\     / \n",
      "1   0   0\n",
      "\n",
      "      7\n",
      "    /   \\\n",
      "  2       6\n",
      " / \\     / \\\n",
      "1   0   0   2\n",
      "\n",
      "                     188\n",
      "                /           \\\n",
      "          68                     158\n",
      "       /     \\                 /     \\\n",
      "    7           38          98         128\n",
      "   / \\         / \\         / \\         / \n",
      " 1     2     0     8     0     6     2 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "mh = MaxHeap(range(3))\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(2)\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(0)\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(6)  # See how nodes were swapped after inserting this value\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(7)\n",
    "print(mh, end='\\n\\n')\n",
    "for i in range(8, 200, 30):\n",
    "    mh.insert(i)\n",
    "print(mh, end='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementacja algorytmu #2 (funkcyjny kopiec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "_left = lambda i: 2 * i + 1\n",
    "_right = lambda i: 2 * i + 2\n",
    "_parent = lambda i: (i - 1) // 2\n",
    "\n",
    "\n",
    "# Swap values in an array in order to satisfy a max-heap property\n",
    "def build_max_heap(values: list):\n",
    "    for i in range(len(values) // 2 - 1, -1, -1):\n",
    "        _heapify_down(values, i, len(values))\n",
    "        \n",
    "        \n",
    "def insert_to_max_heap(heap: list, val: object):\n",
    "    # Add a value as the last node of out Complete Binary Tree\n",
    "    heap.append(val)\n",
    "    # Fix heap in order to satisfy a max-heap property\n",
    "    _heapify_up(heap, len(heap) - 1)\n",
    "    \n",
    "\n",
    "def print_max_heap(heap: list, *args, **kwargs):\n",
    "    print(complete_tree_string(heap), *args, **kwargs)\n",
    "    \n",
    "    \n",
    "def _swap(heap: list, i, j):\n",
    "    heap[i], heap[j] = heap[j], heap[i]\n",
    "    \n",
    "    \n",
    "def _heapify_up(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index' = 0):\n",
    "    while curr_idx > end_idx:\n",
    "        parent_idx = _parent(curr_idx)\n",
    "        if heap[curr_idx] > heap[parent_idx]:\n",
    "            _swap(heap, curr_idx, parent_idx)\n",
    "        curr_idx = parent_idx\n",
    "            \n",
    "    \n",
    "def _heapify_down(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index'):\n",
    "    # Loop till the current node has a child larger than itself\n",
    "    # We assume that when we enter a node which both children are\n",
    "    # smaller than this node, a subtree which a current node is a\n",
    "    # root of must fulfill a max-heap property.\n",
    "    while True:\n",
    "        i = _left(curr_idx)\n",
    "        j = _right(curr_idx)\n",
    "        k = curr_idx\n",
    "        \n",
    "        if i < end_idx:\n",
    "            if heap[i] > heap[k]:\n",
    "                k = i\n",
    "            if j < end_idx and heap[j] > heap[k]:\n",
    "                k = j\n",
    "                \n",
    "        if k == curr_idx: return\n",
    "        # Swap the current with the largest child\n",
    "        heap[curr_idx], heap[k] = heap[k], heap[curr_idx]\n",
    "        curr_idx = k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  2\n",
      " / \\\n",
      "1   0\n",
      "\n",
      "      2\n",
      "    /   \\\n",
      "  2       0\n",
      " / \n",
      "1\n",
      "\n",
      "      2\n",
      "    /   \\\n",
      "  2       0\n",
      " / \\\n",
      "1   0\n",
      "\n",
      "      6\n",
      "    /   \\\n",
      "  2       2\n",
      " / \\     / \n",
      "1   0   0\n",
      "\n",
      "      7\n",
      "    /   \\\n",
      "  2       6\n",
      " / \\     / \\\n",
      "1   0   0   2\n",
      "\n",
      "                     188\n",
      "                /           \\\n",
      "          68                     158\n",
      "       /     \\                 /     \\\n",
      "    7           38          98         128\n",
      "   / \\         / \\         / \\         / \n",
      " 1     2     0     8     0     6     2 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "mh = list(range(3))\n",
    "build_max_heap(mh)\n",
    "print_max_heap(mh, end='\\n\\n')\n",
    "insert_to_max_heap(mh, 2)\n",
    "print_max_heap(mh, end='\\n\\n')\n",
    "insert_to_max_heap(mh, 0)\n",
    "print_max_heap(mh, end='\\n\\n')\n",
    "insert_to_max_heap(mh, 6)\n",
    "print_max_heap(mh, end='\\n\\n')\n",
    "insert_to_max_heap(mh, 7)\n",
    "print_max_heap(mh, end='\\n\\n')\n",
    "for i in range(8, 200, 30):\n",
    "    insert_to_max_heap(mh, i)\n",
    "print_max_heap(mh, end='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Min Heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu #1 (obiektowy kopiec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MinHeap:\n",
    "    def __init__(self, values=None):\n",
    "        if values:\n",
    "            self.heap = list(values) # We make a copy of values in order not to modify them\n",
    "            self.build_heap()\n",
    "        else:\n",
    "            self.heap = []\n",
    "        \n",
    "    def __str__(self):  # A 'complete_tree_string' function is required in order to ensure that printing works\n",
    "        return complete_tree_string(self.heap)\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return bool(self.heap)\n",
    "    \n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def insert(self, val: object):\n",
    "        # Add a value as the last node of out Complete Binary Tree\n",
    "        self.heap.append(val)\n",
    "        # Fix heap in order to satisfy a max-heap property\n",
    "        self._heapify_up(self.heap_size - 1)\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "        \n",
    "    def _heapify_up(self, curr_idx, end_idx=0):\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self.parent_idx(curr_idx)\n",
    "            if self.heap[curr_idx] < self.heap[parent_idx]:\n",
    "                self.swap(curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):\n",
    "        # Loop till the current node has a child larger than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # greater than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a min-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            largest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.heap[l] < self.heap[curr_idx]: \n",
    "                    largest_idx = l\n",
    "                if r < end_idx and self.heap[r] < self.heap[largest_idx]:\n",
    "                    largest_idx = r\n",
    "\n",
    "            if largest_idx != curr_idx:\n",
    "                self.swap(curr_idx, largest_idx)\n",
    "                curr_idx = largest_idx\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "    def build_heap(self):\n",
    "        for i in range(self.heap_size // 2 - 1, -1, -1):\n",
    "            self._heapify_down(i, self.heap_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0\n",
      " / \\\n",
      "1   2\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  1       2\n",
      " / \n",
      "2\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  0       2\n",
      " / \\\n",
      "2   1\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  0       2\n",
      " / \\     / \n",
      "2   1   6\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  0       2\n",
      " / \\     / \\\n",
      "2   1   6   7\n",
      "\n",
      "                      0 \n",
      "                /           \\\n",
      "          0                       2 \n",
      "       /     \\                 /     \\\n",
      "    2           1           6           7 \n",
      "   / \\         / \\         / \\         / \n",
      " 8     38    68    98   128   158   188\n",
      "\n"
     ]
    }
   ],
   "source": [
    "mh = MinHeap(range(3))\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(2)\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(0)\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(6)  # See how nodes were swapped after inserting this value\n",
    "print(mh, end='\\n\\n')\n",
    "mh.insert(7)\n",
    "print(mh, end='\\n\\n')\n",
    "for i in range(8, 200, 30):\n",
    "    mh.insert(i)\n",
    "print(mh, end='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementacja algorytmu #2 (funkcyjny kopiec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "_left = lambda i: 2 * i + 1\n",
    "_right = lambda i: 2 * i + 2\n",
    "_parent = lambda i: (i - 1) // 2\n",
    "\n",
    "\n",
    "# Swap values in an array in order to satisfy a max-heap property\n",
    "def build_min_heap(values: list):\n",
    "    for i in range(len(values) // 2 - 1, -1, -1):\n",
    "        _heapify_down(values, i, len(values))\n",
    "        \n",
    "        \n",
    "def insert_to_min_heap(heap: list, val: object):\n",
    "    # Add a value as the last node of out Complete Binary Tree\n",
    "    heap.append(val)\n",
    "    # Fix heap in order to satisfy a max-heap property\n",
    "    _heapify_up(heap, len(heap) - 1)\n",
    "    \n",
    "\n",
    "def print_min_heap(heap: list, *args, **kwargs):\n",
    "    print(complete_tree_string(heap), *args, **kwargs)\n",
    "    \n",
    "    \n",
    "def _swap(heap: list, i, j):\n",
    "    heap[i], heap[j] = heap[j], heap[i]\n",
    "    \n",
    "    \n",
    "def _heapify_up(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index' = 0):\n",
    "    while curr_idx > end_idx:\n",
    "        parent_idx = _parent(curr_idx)\n",
    "        if heap[curr_idx] < heap[parent_idx]:\n",
    "            _swap(heap, curr_idx, parent_idx)\n",
    "        curr_idx = parent_idx\n",
    "            \n",
    "    \n",
    "def _heapify_down(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index'):\n",
    "    # Loop till the current node has a child larger than itself\n",
    "    # We assume that when we enter a node which both children are\n",
    "    # greater than this node, a subtree which a current node is a\n",
    "    # root of must fulfill a min-heap property.\n",
    "    while True:\n",
    "        i = _left(curr_idx)\n",
    "        j = _right(curr_idx)\n",
    "        k = curr_idx\n",
    "        \n",
    "        if i < end_idx:\n",
    "            if heap[i] < heap[k]:\n",
    "                k = i\n",
    "            if j < end_idx and heap[j] < heap[k]:\n",
    "                k = j\n",
    "                \n",
    "        if k == curr_idx: return\n",
    "        # Swap the current with the largest child\n",
    "        heap[curr_idx], heap[k] = heap[k], heap[curr_idx]\n",
    "        curr_idx = k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0\n",
      " / \\\n",
      "1   2\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  1       2\n",
      " / \n",
      "2\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  0       2\n",
      " / \\\n",
      "2   1\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  0       2\n",
      " / \\     / \n",
      "2   1   6\n",
      "\n",
      "      0\n",
      "    /   \\\n",
      "  0       2\n",
      " / \\     / \\\n",
      "2   1   6   7\n",
      "\n",
      "                      0 \n",
      "                /           \\\n",
      "          0                       2 \n",
      "       /     \\                 /     \\\n",
      "    2           1           6           7 \n",
      "   / \\         / \\         / \\         / \n",
      " 8     38    68    98   128   158   188\n",
      "\n"
     ]
    }
   ],
   "source": [
    "mh = list(range(3))\n",
    "build_min_heap(mh)\n",
    "print_min_heap(mh, end='\\n\\n')\n",
    "insert_to_min_heap(mh, 2)\n",
    "print_min_heap(mh, end='\\n\\n')\n",
    "insert_to_min_heap(mh, 0)\n",
    "print_min_heap(mh, end='\\n\\n')\n",
    "insert_to_min_heap(mh, 6)\n",
    "print_min_heap(mh, end='\\n\\n')\n",
    "insert_to_min_heap(mh, 7)\n",
    "print_min_heap(mh, end='\\n\\n')\n",
    "for i in range(8, 200, 30):\n",
    "    insert_to_min_heap(mh, i)\n",
    "print_min_heap(mh, end='\\n\\n')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}